package Aleehot100;

import org.w3c.dom.Node;

/**
 * ClassName: c032
 * Package: Aleehot100
 * Description: 复制带随机指针的链表
 *
 * @Author BCXJ
 * @Create 2025/6/24 08:36
 * @Version 1.0
 * @Since 1.0
 */
public class c032 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.next = node2;
        node2.next = node3;

        printList(copyRandomList(node1));

    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static void printList(Node node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    // public static Node copyRandomList(Node head) {
    //     if (head == null) {
    //         return null;
    //     }
    //     // 1 - 2 - 3
    //     // 1 - 1' - 2 - 2' - 3 - 3'
    //     Node mid = null, next;
    //     Node cur = head;
    //     while (cur != null) {
    //         mid = new Node(cur.val);
    //         next = cur.next;
    //         cur.next = mid;
    //         mid.next = next;
    //         cur = next;
    //     }

    //     // 设置随机指针
    //     cur = head;

    //     while (cur != null) {
    //         if (cur.random == null) {
    //             cur.next.random = null;
    //             cur = cur.next.next;
    //         } else {
    //             cur.next.random = cur.random.next;
    //             cur = cur.next.next;
    //         }
    //     }

    //     // 新旧链表分离
    //     Node h2 = head.next;
    //     cur = head;
    //     while (cur != null) {
    //         next = cur.next;
    //         cur.next = next.next;
    //         next.next = cur.next == null ? null : next.next.next;
    //         cur = cur.next;
    //     }

    //     return h2;
    // }


    /**
     * 要求时间为O(n)，空间为O(1)
     * @param head
     * @return
     */
    public static Node copyRandomList(Node head) {
        if(head == null) {
            return head;
        }
        Node h = head, h2, next = null, node, mid, head2;
        // 复制单链表
        while(h != null) {
            node = new Node(h.val);
            next = h.next;
            h.next = node;
            node.next = next;
            h = next;
        }

        // 随机指针复制
        h = head;
        while(h != null){
            mid = h.random;
            h.next.random = mid != null ? mid.next : mid;
            h = h.next.next;
        }

        // 断开链表
        h = head; head2 = head.next;
        while(h != null) {
            h2 = h.next;
            h.next = h2.next;
            h = h2.next;
            h2.next = h != null ? h.next : null;
        }
        return head2;
    }





}
